package com.ting.test.algorithms.滑动窗口;

import java.util.LinkedList;

/**
 * 给定一个整型数组arr，和一个整数num
 * 某个arr中的子数组sub，如果想达标，必须满足：
 * sub中最大值 – sub中最小值 <= num，返回arr中达标子数组的数量
 */
public class 返回arr中达标子数组的数量解法1 {
    public static void main(String[] args) {
        int[] arr = new int[]{3, 4, 6, 7, 8, 9, 3};
        int num = 3;
        int result = fun1(arr, 3);
        System.out.println(result);
    }

    /**
     * 将最大值和最小值分别存到一个双端队列中
     *
     * @param arr
     * @param num
     * @return
     */
    private static int fun1(int[] arr, int num) {
        if (arr == null || num < 0) {
            return 0;
        }
        LinkedList<Integer> maxQueue = new LinkedList<>();
        LinkedList<Integer> minQueue = new LinkedList<>();
        int total = 0;
        int L = 0, R = 0;

        while (L<=R) {
            //对于maxQueue，保证单调递减
            while (R < arr.length) {
                while (!maxQueue.isEmpty() && arr[R] >= arr[maxQueue.peekLast()]) {
                    maxQueue.pollLast();
                }
                maxQueue.addLast(R);
                //对于minQueue 保证单调递增
                while (!minQueue.isEmpty() && arr[R] <= arr[minQueue.peekLast()]) {
                    minQueue.pollLast();
                }
                minQueue.addLast(R);
                if (arr[maxQueue.peekFirst()] - arr[minQueue.peekFirst()] > num) {
                    break;
                }
                R++;
            }

            //R=1,L=0
            total += R - L;
            if (L == maxQueue.peekFirst()) {
                maxQueue.pollFirst();
            }
            if (L == minQueue.peekFirst()) {
                minQueue.pollFirst();
            }
            L++;

        }
        return total;
    }
}
